/* 在顺序表中二分查找值为key的元素 */

#include <iostream>
using namespace std;
#include "sqlist.h"

// 二分查找 -- 循环法
int binsearch(Sqlist L, int key)
{
  int low = 0, high = L.length - 1, mid;
  
  // 查找范围合法
  while (low <= high)
  {
    // 中间元素索引
    mid = (low + high) / 2;
    
    // 找到key值
    if (L.data[mid] == key)
      return mid ;
    
    // key值在左半段
    else if (L.data[mid] < key)
      low = mid + 1;
    
    // key值在右半段
    else
      high = mid - 1;
  }
  return -1;
}

// 二分查找key值，low、high表示查找范围 -- 递归法
int bi(Sqlist L, int key, int low, int high)
{
  // 查找范围不合法，查找失败哦
  if (low > high)
    return -1;
  
  // 中间元素索引
  int mid = (low + high) / 2;
  
  // key值在左半段
  if (L.data[mid] < key)
    return bi(L, key, mid + 1, high);
  
  // key值在右半段
  else if (L.data[mid] > key)
    return bi(L, key, low, mid - 1);
  
  // 找到key值
  else
    return mid;
}

int main()
{
  // 创建有序顺序表
  Sqlist L = {{1, 3, 5, 8, 9}, 5};
  
  // 二分查找
  cout << "result is:" << bi(L, 8, 0, 4);
  return 0;
}
